package com.yuw.quick;

public class QuickSortTest {
	public static void main(String[] args) {
		int []a = {9,7,6,5,1,3,4,2};
		quickSort(a, 0, a.length-1);//因为传入的right是最大的下标（如长度为5的数组最大下标为4），所以right=数组长度-1
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+" ");
		}
	}
	public static void quickSort(int[] a, int left, int right) {
		//如果left>right时，元素缺失，left=left时，只剩1个元素，直接返回
		if (left >= right) {
			return;
		}
		int i = left;//定义左查找临时下标
		int j = right;//定义右查找临时下标
		int base = a[i];//定义基准值等于数组的首部
		//当i和j不相遇进行循环
		while(i != j) {
			//从右往左查找，要查找比基准值更小的元素。如果找到就停止，如果没找到（即大于等于）,则继续往前查找
			while(a[j] >= base && i<j) {
				j--;
			}
			//从左向右查找，要查找比基准值更大的元素。如果找到就停止，如果没找到（即小于等于），则继续向后查找
			while(a[i] <= base && i<j) {
				i++;
			}
			//将找到的比基准值base小的值（下标为j）和找到的比基准值大的值（下标为i）的两值进行交换
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
		//到这一步时说明i和j相遇，此时i=j，i（i和j一样，选哪个都无所谓）的左边都是比i小的值，右边都是比i大的值
		//将a[i]给原先设为基准值的下标为left的元素，即a[left]（因为从左向右查找时定义从a[left]开始，
		//然后每次第一次查找的i值=left，因为a[i]要大于base值才会停止，所以继续往前查找，所以a[left]的值不会变化，所以不需要设置临时变量来进行交换）
		//将基准值给a[i]
		a[left] = a[i];
		a[i] = base;
		//递归排序左半序列和右边序列
		//左序列右边界是i-1，有序列左边界是i+1
		quickSort(a, left, i-1);
		quickSort(a,i+1,right);
	}
}
